/**
 * @file 102.LeverOrderTraversal.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-12
 * 
 * @copyright Copyright (c) 2021
 * 
 * 层序遍历十一连
 * 102.二叉树层次遍历
 * 103.二叉树的锯齿状层序遍历
 * 107.二叉树层次遍历II
 * 104.二叉树的最大深度
 * 111.二叉树的最小深度  -- 翻车 -- 最小深度是root到**叶子节点**的最小深度
 * 199.二叉树的右视图
 * 116.填充每个节点的下一个右侧节点指针 -- 节点特殊另开一个文件
 * 117.填充每个节点的下一个右侧节点指针II
 * 637.二叉树的层平均值
 * 515.在每个树行中找最大值
 * 429.N叉树的层序遍历
 * */

#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int val = 0, TreeNode *left = nullptr, TreeNode *right = nullptr)
        : val(val), left(left), right(right) {}
};
class Node // N 叉树
{
public:
    int val;
    vector<Node *> children;
    Node() {}
    Node(int _val)
    {
        val = _val;
    }
    Node(int _val, vector<Node *> _children)
    {
        val = _val;
        children = _children;
    }
};

class Solution
{
public:
    // 102.
    vector<vector<int>> levelOrder(TreeNode *root)
    {
        vector<vector<int>> res;
        queue<TreeNode *> q;
        if (root) {
            q.push(root);
        }
        while (!q.empty()) {
            int n = q.size();
            vector<int> layer;
            for (int i = 0; i < n; ++i) { // for循环遍历一层节点
                TreeNode *node = q.front();
                q.pop();
                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
                layer.push_back(node->val);
            }
            res.emplace_back(layer);
        }
        return res;
    }
    // 103.
    vector<vector<int>> zigzagLevelOrder(TreeNode *root)
    {
        vector<vector<int>> res;
        queue<TreeNode *> que;
        if (root) {
            que.push(root);
        }
        int cnt = 0;
        while (!que.empty()) {
            int length = que.size();
            vector<int> lay;
            for (int i = 0; i < length; ++i) {
                TreeNode *node = que.front();
                que.pop();
                lay.push_back(node->val);
                if (node->left)
                    que.push(node->left);
                if (node->right)
                    que.push(node->right);
            }
            cnt++;
            if (cnt % 2 == 0) {
                reverse(lay.begin(), lay.end());
            }
            res.push_back(lay);
        }
        return res;
    }
    // 107.
    vector<vector<int>> levelOrderBottom(TreeNode *root)
    {
        vector<vector<int>> res;
        queue<TreeNode *> q;
        if (root) {
            q.push(root);
        }
        while (!q.empty()) {
            int n = q.size();
            vector<int> layer;
            for (int i = 0; i < n; ++i) {
                TreeNode *node = q.front();
                layer.push_back(node->val);
                q.pop();
                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
            }
            res.emplace_back(layer);
        }
        std::reverse(res.begin(), res.end());
        return res;
    }
    // 104. 递归求最大值
    int maxDepth(TreeNode *root)
    {
        // 左右子树最大值 + 1 嘛
        if (root == nullptr) {
            return 0;
        }
        return std::max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
    // 104. 层序计数
    int maxDepth2(TreeNode *root)
    {
        // 层序遍历来说，就是最后一层的计数值
        int depth = 0;
        queue<TreeNode *> q;
        if (root) {
            q.push(root);
        }
        while (!q.empty()) {
            ++depth;
            int n = q.size();
            for (int i = 0; i < n; ++i) { // for循环遍历一层节点
                TreeNode *node = q.front();
                q.pop();
                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
            }
        }
        return depth;
    }
    // 111. 递归，多判断语句
    int minDepth(TreeNode *root)
    {
        // 到叶子节点的最小深度
        if (root == nullptr) {
            return 0;
        }
        if (root->left && root->right) { // 左右都有孩子
            return min(minDepth(root->left), minDepth(root->right)) + 1;
        } else if (!root->left && !root->right) { // 左右都无孩子
            return 1;
        } else if (!root->left) {
            return 1 + minDepth(root->right);
        } else {
            return 1 + minDepth(root->left);
        }
    }
    // 111 层序 简单易懂
    int minDepth2(TreeNode *root)
    {
        // 层序遍历来说，找到一个叶子节点即可返回
        int depth = 0;
        queue<TreeNode *> q;
        if (root) {
            q.push(root);
        }
        while (!q.empty()) {
            ++depth;
            int n = q.size();
            for (int i = 0; i < n; ++i) { // for循环遍历一层节点
                TreeNode *node = q.front();
                if (!node->left && !node->right) { // 当前节点是叶子结点诶
                    return depth;
                }
                q.pop();
                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
            }
        }
        return depth;
    }
    // 199.
    vector<int> rightSideView(TreeNode *root)
    {
        // 层序遍历 先右后左 q.front即右节点
        vector<int> res;
        queue<TreeNode *> q;
        if (root) {
            q.push(root);
        }
        while (!q.empty()) {
            res.push_back(q.front()->val);
            int n = q.size();
            for (int i = 0; i < n; ++i) { // for循环遍历一层节点
                TreeNode *node = q.front();
                q.pop();
                if (node->right) {
                    q.push(node->right);
                }
                if (node->left) {
                    q.push(node->left);
                }
            }
        }
        return res;
    }
    // 637.
    vector<double> averageOfLevels(TreeNode *root)
    {
        vector<double> res;
        queue<TreeNode *> q;
        if (root) {
            q.push(root);
        }
        while (!q.empty()) {
            int n = q.size();
            double sum = 0;
            for (int i = 0; i < n; ++i) { // for循环遍历一层节点
                TreeNode *node = q.front();
                sum += node->val;
                q.pop();
                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
            }
            res.push_back(sum / n);
        }
        return res;
    }
    // 515.
    vector<int> largestValues(TreeNode* root) {
        vector<int> res;
        queue<TreeNode *> q;
        if (root) {
            q.push(root);
        }
        while (!q.empty()) {
            int n = q.size();
            int max = INT32_MIN;
            for (int i = 0; i < n; ++i) { // for循环遍历一层节点
                TreeNode *node = q.front();
                max = std::max(max, node->val);
                q.pop();
                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
            }
            res.push_back(max);
        }
        return res;
    }
    // 429.
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> res;
        queue<Node *> q;
        if (root) {
            q.push(root);
        }
        while (!q.empty()) {
            int n = q.size();
            vector<int> layer;
            for (int i = 0; i < n; ++i) {
                Node *node = q.front();
                layer.push_back(node->val);
                q.pop();
                if (!node->children.empty()) {
                    for (Node *child : node->children){
                        q.push(child);
                    }
                }
            }
            res.emplace_back(layer);
        }
        return res;
    }
};